package main

func middleNode(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	slow, fast := head, head

	// 1 -> 2 -> 3
	// fast = 3, slow = 2 => return 2
	// 1 -> 2 -> 3 -> 4
	// fast = nil, slow = 3
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}

	return slow
}
